package 力扣;

/**
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * <p>
 * 示例 1：
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * 示例 2：
 * 输入：s = "cbbd"
 * 输出："bb"
 * 示例 3：
 * 输入：s = "a"
 * 输出："a"
 * 示例 4：
 * 输入：s = "ac"
 * 输出："a"
 *  
 */
public class _5最长回文子串 {
    // dp[i][j] 从第j个字符开始到第i个字符结尾的字符串是否为回文字符串
    public String longestPalindrome(String s) {
        //特判
        if(s == null || s.length() == 0) return "";
        //初始化
        int maxLen = 1;
        int bengin = 0;
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        for(int i = 0; i < len; i ++){
            dp[i][i] = true;
        }
        //遍历
        char[] chars = s.toCharArray();
        for(int j = 1; j < len; j++){
            for(int i = 0; i < j; i++){
                //判断填充dp
                if(chars[i] != chars[j]){
                    dp[i][j] = false;
                }else if(j - i == 1){
                    dp[i][j] = true;
                }else{
                    dp[i][j] = dp[i+1][j-1];
                }
                //更新maxLen和begin
                if(dp[i][j] && j-i+1 > maxLen){
                    maxLen = j-i+1;
                    bengin = i;
                }
            }
        }
        return s.substring(bengin,bengin + maxLen);

    }
}
